#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>

// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template <class K>
struct HashFunc
{
	size_t operator()(const K &key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template <>
struct HashFunc<std::string>
{
	size_t operator()(const std::string &key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE

	};

	template <class K, class V>
	struct HashData
	{
		std::pair<K, V> _kv;
		State _state = EMPTY;
	};

	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const std::pair<K, V> &kv)
		{
			if (Find(kv.first))
				return false;

			if (_n * 10 / _tables.size() >= 7)
			{
				int newsize = _tables.size() * 2;
				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(newsize);

				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state = EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<K, V> *Find(const K &key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();

			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST &&
					_tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K &key)
		{
			HashData<K, V> *ret = Find(key);

			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		std::vector<HashData<K, V>> _tables;
		size_t _n = 0; // 表中存储数据个数
	};

	void HTtest1()
	{
		HashTable<int, int> HT;
		int a[] = {10001, 11, 55, 24, 19, 12, 31};
		for (auto e : a)
		{
			HT.Insert(std::make_pair(e, e));
		}

		std::cout << HT.Find(55) << std::endl;
		std::cout << HT.Find(31) << std::endl;

		HT.Erase(55);
		HT.Erase(31);
		std::cout << HT.Find(55) << std::endl;
		std::cout << HT.Find(31) << std::endl;
	}

	void TestHT2()
	{
		int a[] = {10001, 11, 55, 24, 19, 12, 31};
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(std::make_pair(e, e));
		}

		ht.Insert(std::make_pair(32, 32));
		ht.Insert(std::make_pair(32, 32));
	}

	void TestHT3()
	{
		HashTable<std::string, int> ht;
		ht.Insert(std::make_pair("sort", 1));
		ht.Insert(std::make_pair("left", 1));
		ht.Insert(std::make_pair("insert", 1));

		HashFunc<std::string> HS;
		std::cout << HS("bacd") << std::endl;
		std::cout << HS("abcd") << std::endl;
		std::cout << HS("aadd") << std::endl;
	}

	void test_map1()
	{
		std::string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
							 "苹果", "香蕉", "苹果", "香蕉", "苹果", "草莓", "苹果", "草莓"};
		std::unordered_map<std::string, int> countMap;
		for (auto &e : arr)
		{
			countMap[e]++;
		}

		std::cout << countMap.load_factor() << std::endl;
		std::cout << countMap.max_load_factor() << std::endl;
		std::cout << countMap.size() << std::endl;
		std::cout << countMap.bucket_count() << std::endl;
		std::cout << countMap.max_bucket_count() << std::endl;

		for (auto &kv : countMap)
		{
			std::cout << kv.first << ":" << kv.second << std::endl;
		}
		std::cout << std::endl;
	}
}

namespace hash_bucket
{
	template <class T>
	struct HashNode
	{
		T _data;
		HashNode<T> *_next;

		HashNode(const T &data)
			: _data(data), _next(nullptr)
		{
		}
	};

	template <class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		typedef HashNode<T> Node;

	public:
		// 内部类
		template <class Ptr, class Ref>
		struct __HTIterator
		{
			typedef HashNode<T> Node;
			typedef __HTIterator Self;

			Node *_node;
			const HashTable *_pht;

			__HTIterator(Node *node, const HashTable *pht)
				: _node(node), _pht(pht)
			{
			}

			Ref operator*()
			{
				return _node->_data;
			}

			Ptr operator->()
			{
				return &_node->_data;
			}

			Self &operator++()
			{
				if (_node->_next)
				{
					_node = _node->_next;
				}
				else
				{
					KeyOfT kot;
					Hash hs;
					size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
					++hashi;
					for (; hashi < _pht->_tables.size(); hashi++)
					{
						if (_pht->_tables[hashi])
							break;
					}

					if (hashi == _pht->_tables.size())
					{
						_node = nullptr;
					}
					else
					{
						_node = _pht->_tables[hashi];
					}
				}
				return *this;
			}

			bool operator!=(const Self &s)
			{
				return _node != s._node;
			}
		};

		typedef __HTIterator<T *, T &> iterator;
		typedef __HTIterator<const T *, const T &> const_iterator;

		iterator begin()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this);
				}
			}
			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin() const
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this);
				}
			}
			return end();
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
			_n = 0;
		}

		~HashTable()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node *cur = _tables[i];
				while (cur)
				{
					Node *next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		std::pair<iterator, bool> Insert(const T &data)
		{
			KeyOfT kot;

			iterator it = Find(kot(data));
			if (it != end())
				return std::make_pair(it, false);

			Hash hs;
			if (_n == _tables.size())
			{
				int newsize = _tables.size() * 2;
				HashTable<K, T, KeyOfT, Hash> newHashTable;
				newHashTable._tables.resize(newsize, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node *cur = _tables[i];
					while (cur)
					{
						Node *next = cur->_next;
						size_t hashi = hs(kot(cur->_data)) % newHashTable._tables.size();
						cur->_next = newHashTable._tables[hashi];
						newHashTable._tables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newHashTable._tables);
			}

			size_t hashi = hs(kot(data)) % _tables.size();
			Node *newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return std::make_pair(iterator(newnode, this), true);
		}

		iterator Find(const K &key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node *cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}
				cur = cur->_next;
			}
			return iterator(nullptr, this);
		}

		bool Erase(const K &key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node *prev = nullptr;
			Node *cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		size_t size() const
		{
			size_t cnt = 0;
			for (iterator i = begin(); i != end(); ++i)
			{
				++cnt;
			}
			return cnt;
		}

		bool empty() const
		{
			return size() == 0;
		}
		
	private:
		std::vector<Node *> _tables; // 指针数组
		size_t _n;
	};
}